//============================================================================
// Name        : BucketSort.cpp
// Author      : Oasis
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;
struct node{
	int val;
	node* next;
};
void bucket(int data[],int length,node ** table);

int main() {
	int data[] = {98,99,90,2,1,7,56,4,34,67,31,78,75,54,64,57,89,39,16,40};
	int length = 20;
	int size = 10;
	node** table = new node*[size];
	for(int i=0;i<size;i++){  //initialize to all zero
		table[i]=0;
	}
    bucket(data,length,table);
    for(int i=0;i<size;i++){  //print all
    	node *p = table[i];
    	while(p!=0){
    		cout<<" "<<p->val;
    		p = p->next;
    	}
    	cout<<endl;
    }
	return 0;
}
void bucket(int data[],int length,node ** table){
	int pos;
	node *p,*pre;
	for(int i=0;i<length;i++){
		pos = data[i]/10;
		if(table[pos]==0||table[pos]->val>data[i]){
			node *temp = table[pos];
			table[pos] = new node;
			table[pos]->val = data[i];
			table[pos]->next = temp;
		}
		else{
			p = table[pos];
			pre = p;
			while(p!=0){
				if(p->val<data[i]){
					pre = p;
					p = p->next;
					continue;
				}
				else{
					break;
				}
			}
			node* temp = p;
			pre->next = new node;
			pre->next->val = data[i];
			pre->next->next = temp;
		}
	}
}
